5282. Saddle points

 

The matrix A is given. It contains n rows and m columns. The saddle point of the matrix is an element that is minimum in its row and maximum in its column.

Find the number of saddle points in a given matrix.

 

Input. The first line contains two integers n and m (1 ≤ n, m ≤ 750). Then given n rows with m numbers in each. The j-th number of the i-th line equals Aij. All Aij do not exceed 1000 by absolute value.

 

Output. Print the number of saddle points.

 

Sample input 1

Sample output 1

2 2

0 0

0 0

4

 

 

Sample input 2

Sample output 2

3 4

7 1 5 3

3 2 6 4

5 2 8 6

2

 

 

SOLUTION

arrays

 

Algorithm analysis

Let minRow be an array where minRow[i] contains the minimum value of the i-th row.

Let maxCol be an array where maxCol[i] contains the maximum value of the i-th column.

The number of saddle points equals the number of such Aij for which Aij = minRow[i] and Aij = maxCol[j].

 

Example

Consider the second sample. It contains 2 saddle points.

 

Algorithm realization

Store the input matrix in a two-dimensional integer array a. Declare the arrays minRow and maxCol.

 

#define MAX 800

int a[MAX][MAX];

int minRow[MAX], maxCol[MAX];

 

Read the input matrix.

 

scanf("%d %d",&n,&m);

for(i = 0; i < n; i++)

for(j = 0; j < m; j++)

  scanf("%d",&a[i][j]);    

 

For each i-th row, find the minimum element and store it in minRow[i].

 

for(i = 0; i < n; i++)

{

  minRow[i] = 1000;

  for(j = 0; j < m; j++)

    if(a[i][j] < minRow[i]) minRow[i] = a[i][j];

}

 

For each j-th column, find the maximum element and store it in maxCol[j].

 

for(j = 0; j < m; j++)

{

  maxCol[j] = -1000;

  for(i = 0; i < n; i++)

    if(a[i][j] > maxCol[j]) maxCol[j] = a[i][j];

}

 

In the variable res compute the number of aij, for which aij = minRow[i] and aij = maxCol[j].

 

res = 0;

for(i = 0; i < n; i++)

for(j = 0; j < m; j++)

  if ((a[i][j] == minRow[i]) && (a[i][j] == maxCol[j])) res++;

 

Print the number of saddle points.

 

printf("%d\n",res);

 

Algorithm realization – double pointer

 

#include <stdio.h>

#define MAX 800

 

int n, m, i, j, res;

int *minRow, *maxCol;

int **a;

 

int main(void)

{

  scanf("%d %d", &n, &m);

  a = new int*[n];

  for (i = 0; i < n; i++)

  {

    a[i] = new int[m];

    for (j = 0; j < m; j++)

      scanf("%d", &a[i][j]);

  }

 

  minRow = new int[n];

  for (i = 0; i < n; i++)

  {

    minRow[i] = 1000;

    for (j = 0; j < m; j++)

      if (a[i][j] < minRow[i]) minRow[i] = a[i][j];

  }

 

  maxCol = new int[m];

  for (j = 0; j < m; j++)

  {

    maxCol[j] = -1000;

    for (i = 0; i < n; i++)

      if (a[i][j] > maxCol[j]) maxCol[j] = a[i][j];

  }

 

  res = 0;

  for (i = 0; i < n; i++)

  for (j = 0; j < m; j++)

    if ((a[i][j] == minRow[i]) && (a[i][j] == maxCol[j])) res++;

 

  printf("%d\n", res);

 

  for (i = 0; i < n; i++)

    delete[] a[i];

  delete[] a;

  delete[] minRow;

  delete[] maxCol;

 

  return 0;

}

 

Java realization

 

import java.util.*;

 

public class Main

{

  public static void main(String []args)

  {

    Scanner con = new Scanner(System.in);

    int n = con.nextInt();

    int m = con.nextInt();

     

    int a[][] = new int[n][m];

    for(int i = 0; i < n; i++)

    for(int j = 0; j < m; j++)

      a[i][j] = con.nextInt();

 

    int minRow[] = new int[n];

    for(int i = 0; i < n; i++)

    {

      minRow[i] = 1000;

      for(int j = 0; j < m; j++)

        if(a[i][j] < minRow[i]) minRow[i] = a[i][j];

    }

 

    int maxCol[] = new int[m];

    for(int j = 0; j < m; j++)

    {

      maxCol[j] = -1000;

      for(int i = 0; i < n; i++)

        if(a[i][j] > maxCol[j]) maxCol[j] = a[i][j];

    }

   

    int res = 0;

    for(int i = 0; i < n; i++)

    for(int j = 0; j < m; j++)

      if ((a[i][j] == minRow[i]) && (a[i][j] == maxCol[j])) res++;

   

    System.out.println(res);

    con.close();

  }

}